#include "k_median.h"
#include <algorithm>
#include <sstream>
#include <cfloat>

namespace wh
{
	inline double get_min(double a, double b) { return a < b ? a : b; };
	void check_file(const std::ifstream& fin, const std::string& name)
	{
		if (!fin.is_open())
		{
			std::cerr << "I can't open the file: " << name << std::endl;
			std::cin.get();
			std::exit(1);
		}
	}

	void check_file(const std::ofstream& fout, const std::string& name)
	{
		if (!fout.is_open())
		{
			std::cerr << "I can't open the file: " << name << std::endl;
			std::cin.get();
			std::exit(1);
		}
	}
	void eat_line(std::istream& fin)
	{
		char temp;
		while (temp = fin.get())
		{
			if (temp == '\n' || temp == EOF)
				break;
		}
	}

	// 该函数用于当已经选出目标数量的候选设施时，删除其余的候选设施
	void delete_candidate(wh::ref_nearest_dist_map& dist_map, std::unordered_set<int>& candidate_id)
	{
		for (auto c : candidate_id)
			dist_map.erase(c);
	}

	void print_dist(const fac_ref_dist_map& fac_ref_dist, const std::vector<std::tuple<int, int, int, double, double, double>>& ref_info, std::map<int, double>& dist_map)
	{
		std::vector<std::pair<double, int>> dist;
		for (auto i : ref_info)
		{
			int r_id = std::get<0>(i);
			std::string name("F:/大四课程/毕业设计/MILE-RUN-master/datasets/CA_datasets/tmp/");
			name += std::to_string(r_id);
			name += ".txt";
			std::ofstream fout(name);
			check_file(fout, name);
			for (auto f : dist_map)
				dist.push_back(std::make_pair(fac_ref_dist.at(f.first).at(r_id), f.first));
			std::sort(dist.begin(), dist.end());
			for (auto d : dist)
				fout << "id: " << d.second << "\tdist: " << d.first << std::endl;
			dist.clear();
			fout.close();
		}
	}

	void print_prob(std::vector<std::tuple<int, int, int, double, double, double>>& ref_info)
	{
		std::string name("F:/大四课程/毕业设计/MILE-RUN-master/datasets/CA_datasets/tmp/prob.txt");
		std::ofstream fout(name);
		check_file(fout, name);
		for (auto i : ref_info)
		{
			int r_id = std::get<0>(i);
			double p = std::get<5>(i);
			fout << r_id << "  " << p << std::endl;
		}
		fout.close();
	}

	/********************* struct Config ********************
	/*
	/* 结构体 Config 的成员函数
	/*
	/********************* struct Config ********************/
	void Config::init(const std::string& config_file)
	{
		std::ifstream fin(config_file);
		if (!fin.is_open())
		{
			std::cerr << "Config 结构初始化失败，我无法打开文件!!!";
			std::cin.get();
			std::exit(1);
		}
		std::string temp;
		while (std::getline(fin, temp))//通过这个循环读取配置文件，每次读取一行（即一个配置）
		{
			std::stringstream ss(temp);
			std::string str_param;
			ss >> str_param;
			if (str_param == "is_directed_graph")
				ss >> is_directed_graph;
			else if (str_param == "edge")
				ss >> edge_file;
			else if (str_param == "facility")
				ss >> facility_file;
			else if (str_param == "candidate")
				ss >> candidate_file;
			else if (str_param == "reference")
				ss >> refloc_file;
			else if (str_param == "K")
				ss >> K;
			else if (str_param == "result")
			{
				ss >> result_file;
				result_file += ".bab.txt";
			}
			else if (str_param == "rate")
			{
				ss >> rate;
			}
			else if (str_param == "fac_id")
				ss >> fac_id;
            
		}
        time_file = "timeRecord_tmp.txt";
		fin.close();
	}


	//	recorded_facility: 记录着已经找到的设施集
	double fast_greedy(std::map<int, double>& dist_map, wh::fac_ref_dist_map& fac_ref_dist, const wh::reference_info_list& ref_info, wh::ref_nearest_dist_map& dist_old, wh::ref_nearest_dist_map & dist_new, std::vector<int>& r_change, std::set<int>& saved_f, const int times, const std::string result_file_path, std::unordered_set<int>& candidate_id, std::vector<std::pair<int, double>>& recorded_facility)
	{
		std::ofstream fout(result_file_path, std::ios_base::out|std::ios_base::app);
		wh::check_file(fout, result_file_path);
        double res_dist;

		// 首先输出已经找到的设施集
		int i = 0;
		for (;i<recorded_facility.size(); ++i)
		{
			std::pair<int, double>& record = recorded_facility[i];
			fout << "第" << i + 1 << "个最近设施是：" << record.first << "\t最近距离为：" << record.second << std::endl;
			std::cout << "第" << i + 1 << "个最近设施是：" << record.first << "\t最近距离为：" << record.second << std::endl;
		}

		// 开始寻找新的设施
		for (; i < times; i++) // 一共需要查找多少次，次数是已有设施的个数
		{
			int op_id = -1;  // 最优的设施 id
			double op_dist = DBL_MAX;  // 当前最近距离的值
			for (auto f : dist_map) // 每一次查找都需遍历所有的候选设施
			{
				double dist_change = 0.0;
				double dist;
				int f_id = f.first;
				for (auto r : r_change) // 对每一个设施，遍历那些最近距离发生了改变的参考位置
				{
					dist_change = dist_change - get_min(dist_old[r], fac_ref_dist[f_id][r])
						+ get_min(dist_new[r], fac_ref_dist[f_id][r]);
				}
				dist = dist_map[f_id] + dist_change; // 更新距离和
				dist_map[f_id] = dist;
				if (dist < op_dist)
				{
					op_dist = dist;
					op_id = f_id;
				}
			}
			fout << "第" << i + 1 << "个最近设施是：" << op_id << "\t最近距离为：" << op_dist << std::endl;
			std::cout << "第" << i + 1 << "个最近设施是：" << op_id << "\t最近距离为：" << op_dist << std::endl;
			recorded_facility.push_back(std::make_pair(op_id, op_dist));  // 记录新的找到的设施
            res_dist = op_dist;

			dist_map.erase(op_id); // 将找到的最近设施从 dist_map 中删除，下次就不会再次访问它
			saved_f.insert(op_id); // 记录这个设施的id，这些设施是进行LNB算法的初始设施
			r_change.clear();
			dist_old.swap(dist_new);  // dist_old 和 dist_new 进行交换，此时 dist_old 是比较新的， dist_new 则是旧的，下面 dist_new 取得了dist_old和新设施之间的最小值，所以可以进行交换

			for (auto r : ref_info) // 寻找出最小距离发生改变的参考位置
			{
				int r_id = std::get<0>(r);
				double d1 = dist_old[r_id];  // 参考位置与原来最近设施的位置
				double d2 = fac_ref_dist[op_id][r_id];  // 参考位置与新加入的设施之间的位置，如果新的位置更小，那么它的最小距离发生了改变
				dist_new[r_id] = get_min(d1, d2);  
				if (d2 < d1)
					r_change.push_back(r_id);
			}

			// 如果选出的是候选设施
			if (candidate_id.find(op_id) != candidate_id.end())
			{
				candidate_id.erase(op_id);
				auto dist_map_temp = dist_map;
				auto dist_old_temp = dist_old;
				auto dist_new_temp = dist_new;
				auto r_change_temp = r_change;
				delete_candidate(dist_map_temp, candidate_id);
				++i;  // i+1是为了在子函数中的输出能够在原来的基础上加1
				res_dist = fast_greedy_assistant(dist_map_temp, fac_ref_dist, ref_info, dist_old_temp, dist_new_temp, saved_f, i, times, fout, r_change_temp);
				break;
			}
		}
		fout << "#\n";
        fout.close();
        return res_dist;
	}


	// 作为 fast_greedy 的辅助函数，当 fast_greedy 找到指定数量的候选设施后，开始执行该函数
	// Args:
	//		dist_map: 每个设施与所有用户的距离
	//		fac_ref_dist: 设施和参考位置之间的距离映射表
	//		ref_info: 记录着参考位置的有关信息
	//		dist_old: 每个参考位置原最近设施的距离
	//		dist_new: 每个参考位置现最近设施的距离
	//		saved_f: 记录着被选出的设施 id
	//		i: 已经选出的设施个数
	//		times: 需要选出的设施个数
	//		fout: 输出文件的指针
	//		r_change: 记录着最近设施发生改变的参考位置的编号
	double fast_greedy_assistant(std::map<int, double> &dist_map, wh::fac_ref_dist_map& fac_ref_dist, const wh::reference_info_list& ref_info, wh::ref_nearest_dist_map &dist_old, wh::ref_nearest_dist_map &dist_new, std::set<int>& saved_f,int i, const int times, std::ofstream& fout, std::vector<int> &r_change)
	{
        double res_dist;
		for (; i < times; i++) // 一共需要查找多少次，次数是已有设施的个数
		{
			int op_id = -1;  // 最优的设施 id
			double op_dist = DBL_MAX;  // 当前最近距离的值
			for (auto &f : dist_map) // 每一次查找都需遍历所有的候选设施
			{
				double dist_change = 0.0;
				double dist;
				int f_id = f.first;
				for (auto r : r_change) // 对每一个设施，遍历那些最近距离发生了改变的参考位置
				{
					dist_change = dist_change - get_min(dist_old[r], fac_ref_dist[f_id][r])
						+ get_min(dist_new[r], fac_ref_dist[f_id][r]);
				}
				dist = dist_map[f_id] + dist_change; // 更新距离和
				dist_map[f_id] = dist;
				if (dist < op_dist)
				{
					op_dist = dist;
					op_id = f_id;
				}
			}
			fout << "第" << i + 1 << "个最近设施是：" << op_id << "\t最近距离为：" << op_dist << std::endl;
			std::cout << "第" << i + 1 << "个最近设施是：" << op_id << "\t最近距离为：" << op_dist << std::endl;
            res_dist = op_dist;

			dist_map.erase(op_id); // 将找到的最近设施从 dist_map 中删除，下次就不会再次访问它
			saved_f.insert(op_id); // 记录这个设施的id，这些设施是进行LNB算法的初始设施
			r_change.clear();
			dist_old.swap(dist_new);  // dist_old 和 dist_new 进行交换，此时 dist_old 是比较新的， dist_new 则是旧的，下面 dist_new 取得了dist_old和新设施之间的最小值，所以可以进行交换

			for (auto r : ref_info) // 寻找出最小距离发生改变的参考位置
			{
				int r_id = std::get<0>(r);
				double d1 = dist_old[r_id];  // 参考位置与原来最近设施的位置
				double d2 = fac_ref_dist[op_id][r_id];  // 参考位置与新加入的设施之间的位置，如果新的位置更小，那么它的最小距离发生了改变
				dist_new[r_id] = get_min(d1, d2);  
				if (d2 < d1)
					r_change.push_back(r_id);
			}
		}
        return res_dist;
	}


	void transfer_fac_to_can(wh::facility_info_map& facility_info, wh::candidate_info_map& candidate_info,const std::set<int>& saved_f)
	{
		for (auto iter = facility_info.begin(); iter != facility_info.end();) // 遍历所有的设施信息，需要保留的保留，其余的移入候选设施并从表中删除
		{
			if (saved_f.find(iter->first) == saved_f.end()) // 如果这个设施没能在 saved_f 中找到，需要将它移除到候选设施中
			{
				candidate_info[iter->first + 10000] = iter->second;
				facility_info.erase(iter++);
			}
			else
				iter++;
		}
	}

	double get_dist(const std::map<int, std::pair<int, double>>& ref_dist, const reference_info_list& ref_info)
	{
		double res = 0.0;
		for (auto i : ref_info)
		{
			int id = std::get<0>(i);
			double prob = std::get<5>(i);
			res += ref_dist.at(id).second * prob;
		}
		return res;
	}

}
